#include <ngx_config.h>
#include <ngx_core.h>
#include <ngx_http.h>

#define SHM_NAME_LEN 256




//每一个peer都有相应的共享内存项
typedef struct {
    ngx_pid_t                                owner;

    ngx_msec_t                               access_time;
    ngx_int_t                               speeds;

    ngx_shmtx_t                              mutex;
    ngx_shmtx_sh_t                           lock;

    struct sockaddr                         *sockaddr;
    socklen_t                                socklen;
} ngx_http_upstream_fastest_peer_shm_t;

//保存所有peer的共享内存
typedef struct {
    ngx_uint_t                               generation;
   	ngx_uint_t                               fastestHashSum;

    ngx_uint_t                               number;

    ngx_http_upstream_fastest_peer_shm_t       peers[1];
} ngx_http_upstream_fastest_peers_shm_t;


typedef struct ngx_http_upstream_fastest_peer_s ngx_http_upstream_fastest_peer_t;

typedef ngx_int_t (*ngx_http_upstream_fastest_packet_init_pt)
    (ngx_http_upstream_fastest_peer_t *peer);
typedef ngx_int_t (*ngx_http_upstream_fastest_packet_parse_pt)
    (ngx_http_upstream_fastest_peer_t *peer);
typedef void (*ngx_http_upstream_fastest_packet_clean_pt)
    (ngx_http_upstream_fastest_peer_t *peer);

//每一个peer的信息
struct ngx_http_upstream_fastest_peer_s{
    ngx_flag_t                               state;
    ngx_pool_t                              *pool;
    ngx_uint_t                               index;
    ngx_uint_t                               max_busy;
    ngx_str_t                               *upstream_name;
    ngx_addr_t                              *fastest_peer_addr;
    ngx_addr_t                              *peer_addr;
    ngx_event_t                              fastest_ev;
    ngx_event_t                              fastest_timeout_ev;
    ngx_peer_connection_t                    pc;

    void                                    *fastest_data;
    ngx_event_handler_pt                     send_handler;
    ngx_event_handler_pt                     recv_handler;

    ngx_http_upstream_fastest_packet_init_pt   init;
    ngx_http_upstream_fastest_packet_parse_pt  parse;
    ngx_http_upstream_fastest_packet_clean_pt  reinit;

    ngx_http_upstream_fastest_peer_shm_t      *shm;

};

//所有peer的信息，包括其共享内存
typedef struct {
	ngx_uint_t                               fastestHashSum;   //用于区别版本

	ngx_str_t                                fastest_shm_name;
	ngx_array_t                              peers;

    ngx_http_upstream_fastest_peers_shm_t     *peers_shm;

} ngx_http_upstream_fastest_peers_t;


typedef struct {

	ngx_http_upstream_fastest_peers_t         *peers;

} ngx_http_upstream_fastest_main_conf_t;



typedef struct {
    /* the round robin data must be first */
    ngx_http_upstream_rr_peer_data_t   rrp;

    //ngx_http_upstream_fastest_peers_shm_t      *peers_shm;

    ngx_str_t                               *upstream_name;

    ngx_event_get_peer_pt              get_rr_peer;
    ngx_event_free_peer_pt             free_rr_peer;
} ngx_http_upstream_fastest_peer_data_t;


#define NGX_HTTP_FASTEST_CONNECT_DONE          0x0001
#define NGX_HTTP_FASTEST_SEND_DONE             0x0002
#define NGX_HTTP_FASTEST_RECV_DONE             0x0004
#define NGX_HTTP_FASTEST_ALL_DONE              0x0008



static void *ngx_http_upstream_fastest_create_main_conf(ngx_conf_t *cf);
static char *ngx_http_upstream_fastest_init_main_conf(ngx_conf_t *cf, void *conf);

//共享内存处理
static char * ngx_http_upstream_fastest_init_shm(ngx_conf_t *cf, void *conf);
static ngx_int_t ngx_http_upstream_fastest_init_shm_zone(ngx_shm_zone_t *shm_zone, void *data);
static ngx_int_t ngx_http_upstream_fastest_init_shm_peer(ngx_http_upstream_fastest_peer_shm_t *psh, 
	ngx_http_upstream_fastest_peer_shm_t *opsh,
    ngx_pool_t *pool, ngx_str_t *name);
static ngx_http_upstream_fastest_peer_shm_t * ngx_http_upstream_fastest_find_shm_peer(ngx_http_upstream_fastest_peers_shm_t *p,
    ngx_addr_t *addr);
static ngx_int_t ngx_http_upstream_fastest_get_shm_name(ngx_str_t *shm_name, ngx_pool_t *pool, ngx_uint_t generation);
static ngx_shm_zone_t * ngx_shared_memory_find(ngx_cycle_t *cycle, ngx_str_t *name, void *tag);


static char *ngx_http_upstream_fastest(ngx_conf_t *cf, ngx_command_t *cmd, void *conf);
static ngx_int_t ngx_http_upstream_init_fastest_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us);
static ngx_int_t ngx_http_upstream_get_fastest_peer(ngx_peer_connection_t *pc, void *data);
ngx_int_t ngx_http_upstream_fastest_add_peers(ngx_conf_t *cf, void *conf);
ngx_int_t ngx_http_upstream_fastest_add_peer(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us, ngx_addr_t *peer_addr);


static char * ngx_http_upstream_fastest_status(ngx_conf_t *cf, ngx_command_t *cmd, void *conf);
static ngx_int_t ngx_http_upstream_fastest_status_handler(ngx_http_request_t *r);
static void ngx_http_upstream_fastest_status_json_format(ngx_buf_t *b, ngx_http_upstream_fastest_peers_t *peers);

static ngx_int_t ngx_http_upstream_fastest_init_process(ngx_cycle_t *cycle);
static ngx_int_t ngx_http_upstream_fastest_add_timers(ngx_cycle_t *cycle);
static void ngx_http_upstream_fastest_begin_handler(ngx_event_t *event);
static void ngx_http_upstream_fastest_connect_handler(ngx_event_t *event);
static void ngx_http_upstream_fastest_timeout_handler(ngx_event_t *event);
static void ngx_http_upstream_fastest_peek_handler(ngx_event_t *event);
static void ngx_http_upstream_fastest_status_update(ngx_http_upstream_fastest_peer_t *peer, ngx_int_t result);
static ngx_int_t ngx_http_upstream_fastest_need_exit();
static void ngx_http_upstream_fastest_clear_all_events();
static void ngx_http_upstream_fastest_clean_event(ngx_http_upstream_fastest_peer_t *peer);
static void ngx_http_upstream_fastest_finish_handler(ngx_event_t *event);


static ngx_command_t ngx_http_upstream_fastest_commands[] = {
   			
   	{ ngx_string("fastest"),
      NGX_HTTP_UPS_CONF|NGX_CONF_NOARGS,
      ngx_http_upstream_fastest,
      0,
      0,
      NULL },

    //显示服务器的状态页面
    { ngx_string("fastest_status"),
      NGX_HTTP_LOC_CONF|NGX_CONF_NOARGS,
      ngx_http_upstream_fastest_status,
      0,
      0,
      NULL },

      ngx_null_command
};

static ngx_http_module_t  ngx_http_upstream_fastest_module_ctx = {
    NULL,                         				   /* preconfiguration */
    NULL,                		   				   /* postconfiguration */

    ngx_http_upstream_fastest_create_main_conf,    /* create main configuration */
    ngx_http_upstream_fastest_init_main_conf,      /* init main configuration */

    NULL,                          				   /* create server configuration */
    NULL,                          				   /* merge server configuration */

    NULL,						   				   /* create location configuration */
    NULL  						   				   /* merge location configuration */
};


ngx_module_t  ngx_http_upstream_fastest_module = {
    NGX_MODULE_V1,
    &ngx_http_upstream_fastest_module_ctx,    				/* module context */
    ngx_http_upstream_fastest_commands,       				/* module directives */
    NGX_HTTP_MODULE,               							/* module type */
    NULL,                          							/* init master */
    NULL,                          							/* init module */
    ngx_http_upstream_fastest_init_process,                 /* init process */
    NULL,                          							/* init thread */
    NULL,                          							/* exit thread */
    NULL,                          							/* exit process */
    NULL,                          							/* exit master */
    NGX_MODULE_V1_PADDING
};


static ngx_uint_t ngx_http_upstream_fastest_shm_generation = 0;
static ngx_http_upstream_fastest_peers_t *fastest_peers_ctx = NULL;




static void *
ngx_http_upstream_fastest_create_main_conf(ngx_conf_t *cf)
{
    ngx_http_upstream_fastest_main_conf_t  *ufmcf;

    ufmcf = ngx_pcalloc(cf->pool, sizeof(ngx_http_upstream_fastest_main_conf_t));
    if (ufmcf == NULL) {
        return NULL;
    }

    ufmcf->peers = ngx_pcalloc(cf->pool,
                               sizeof(ngx_http_upstream_fastest_peers_t));
    if (ufmcf->peers == NULL) {
        return NULL;
    }

    ufmcf->peers->fastestHashSum=0;

    if (ngx_array_init(&ufmcf->peers->peers, cf->pool, 16,
                       sizeof(ngx_http_upstream_fastest_peer_t)) != NGX_OK)
    {
        return NULL;
    }

    return ufmcf;
}

static char *
ngx_http_upstream_fastest_init_main_conf(ngx_conf_t *cf, void *conf)
{

    if (ngx_http_upstream_fastest_add_peers(cf, conf) != NGX_OK) {
        return NGX_CONF_ERROR;
    }

    return ngx_http_upstream_fastest_init_shm(cf, conf);
}

ngx_int_t ngx_http_upstream_fastest_add_peers(ngx_conf_t *cf, void *conf){

	ngx_uint_t i,n;
	ngx_http_upstream_srv_conf_t **uscfp;
	ngx_http_upstream_server_t *server;
	ngx_http_upstream_main_conf_t  *umcf;

    umcf = ngx_http_conf_get_module_main_conf(cf, ngx_http_upstream_module);
    uscfp = umcf->upstreams.elts;

    for (i = 0; i < umcf->upstreams.nelts; i++) {

    	server = uscfp[i]->servers->elts;

    	for (n = 0; n < uscfp[i]->servers->nelts; n++)
    	{
    		if(ngx_http_upstream_fastest_add_peer(cf,uscfp[i],server[n].addrs) == NGX_ERROR){

    			ngx_log_error(NGX_LOG_EMERG, cf->log, 0,
                  "http upstream fastest add peer error ,peer addr");
    			return NGX_ERROR;
    		};
    	}

    }

    return NGX_OK;
}

ngx_int_t
ngx_http_upstream_fastest_add_peer(ngx_conf_t *cf,
    ngx_http_upstream_srv_conf_t *us, ngx_addr_t *peer_addr)
{
    ngx_http_upstream_fastest_peer_t       *peer;
    ngx_http_upstream_fastest_peers_t      *peers;

    ngx_http_upstream_fastest_main_conf_t  *ufmcf;

    if (us->srv_conf == NULL) {

        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, cf->log, 0,
                       "tag:peer us->srv_conf == NULL");
        return NGX_ERROR;
    }

    ufmcf = ngx_http_conf_get_module_main_conf(cf,
                                               ngx_http_upstream_fastest_module);
    peers = ufmcf->peers;

    peer = ngx_array_push(&peers->peers);
    if (peer == NULL) {

        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, cf->log, 0,
                       "tag:peer ngx_array_push(&peers->peers) == NULL");
        return NGX_ERROR;
    }

    ngx_memzero(peer, sizeof(ngx_http_upstream_fastest_peer_t));

    peer->index = peers->peers.nelts - 1;
    peer->upstream_name = &us->host;
    peer->peer_addr = peer_addr;

    peers->fastestHashSum +=
        ngx_murmur_hash2(peer_addr->name.data, peer_addr->name.len);

    return peer->index;
}


//-----------------------------------初始化共享内存-----------------------------

static char * ngx_http_upstream_fastest_init_shm(ngx_conf_t *cf, void *conf){
    ngx_str_t                            *shm_name;
    ngx_uint_t                            shm_size;
    ngx_shm_zone_t                       *shm_zone;
    ngx_http_upstream_fastest_main_conf_t  *ufmcf = conf;

    if (ufmcf->peers->peers.nelts > 0) {

        ngx_http_upstream_fastest_shm_generation++;

        shm_name = &ufmcf->peers->fastest_shm_name;

        ngx_http_upstream_fastest_get_shm_name(shm_name, cf->pool,
                                    ngx_http_upstream_fastest_shm_generation);

        /* The default shared memory size is 1M */
        shm_size = 1 * 1024 * 1024;

        shm_zone = ngx_shared_memory_add(cf, shm_name, shm_size,
                                         &ngx_http_upstream_fastest_module);

        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, cf->log, 0,
                       "http upstream fastest, upsteam:%V, shm_zone size:%ui",
                       shm_name, shm_size);

        shm_zone->data = cf->pool;
        fastest_peers_ctx = ufmcf->peers;

        shm_zone->init = ngx_http_upstream_fastest_init_shm_zone;
    }
    else {
         fastest_peers_ctx = NULL;
    }

    return NGX_CONF_OK;
}


static ngx_int_t ngx_http_upstream_fastest_init_shm_zone(ngx_shm_zone_t *shm_zone, void *data){
    size_t                               size;
    ngx_str_t                            oshm_name;
    ngx_int_t                            rc;
    ngx_uint_t                           i, same, number;
    ngx_pool_t                          *pool;
    ngx_shm_zone_t                      *oshm_zone;
    ngx_slab_pool_t                     *shpool;
 
    ngx_http_upstream_fastest_peer_t      *peer;
    ngx_http_upstream_fastest_peers_t     *peers;

    ngx_http_upstream_fastest_peer_shm_t  *peer_shm, *opeer_shm;
    ngx_http_upstream_fastest_peers_shm_t *peers_shm, *opeers_shm;

    opeers_shm = NULL;
    peers_shm = NULL;

    same = 0;
    peers = fastest_peers_ctx;
    if (peers == NULL) {
        return NGX_OK;
    }

    number = peers->peers.nelts;
    if (number == 0) {
        return NGX_OK;
    }

    pool = shm_zone->data;
    if (pool == NULL) {
        pool = ngx_cycle->pool;
    }

    shpool = (ngx_slab_pool_t *) shm_zone->shm.addr;

    //如果传进了data，所以nginx进行了reload操作，data保存了旧版本的数据，所以需要检查是否和新的数据一致
    if (data) {
        opeers_shm = data;

        if ((opeers_shm->number == number)
            && (opeers_shm->fastestHashSum == peers->fastestHashSum)) {

            peers_shm = data;
            same = 1;
        }
    }

    if (!same) {

        if (ngx_http_upstream_fastest_shm_generation > 1) {

        	//获取上一个版本的共享内存名字oshm_name
            ngx_http_upstream_fastest_get_shm_name(&oshm_name, pool, ngx_http_upstream_fastest_shm_generation - 1);

            /* The global variable ngx_cycle still points to the old one */
            oshm_zone = ngx_shared_memory_find((ngx_cycle_t *) ngx_cycle,
                                               &oshm_name,
                                               &ngx_http_upstream_fastest_module);

            if (oshm_zone) {
                opeers_shm = oshm_zone->data;

                ngx_log_debug2(NGX_LOG_DEBUG_HTTP, shm_zone->shm.log, 0,
                               "http upstream fastest, find oshm_zone:%p, "
                               "opeers_shm: %p",
                               oshm_zone, opeers_shm);
            }
        }

        size = sizeof(*peers_shm) +
               (number - 1) * sizeof(ngx_http_upstream_fastest_peer_shm_t);

        //分配共享内存
        peers_shm = ngx_slab_alloc(shpool, size);

        if (peers_shm == NULL) {
            goto failure;
        }

        ngx_memzero(peers_shm, size);
    }

    peers_shm->generation = ngx_http_upstream_fastest_shm_generation;
    peers_shm->fastestHashSum = peers->fastestHashSum;
    peers_shm->number = number;

    peer = peers->peers.elts;

    //初始化每一个peer的共享内存值，若有旧值则沿用

    for (i = 0; i < number; i++) {

        peer_shm = &peers_shm->peers[i];

        /*
         * This function may be triggered before the old stale
         * work process exits. The owner may stick to the old
         * pid.
         */
        peer_shm->owner = NGX_INVALID_PID;

        if (same) {
            continue;
        }

        peer_shm->socklen = peer[i].peer_addr->socklen;
        peer_shm->sockaddr = ngx_slab_alloc(shpool, peer_shm->socklen);
        if (peer_shm->sockaddr == NULL) {
            goto failure;
        }

        ngx_memcpy(peer_shm->sockaddr, peer[i].peer_addr->sockaddr,
                   peer_shm->socklen);

        //有旧值,根据旧值来初始化对应的peer

        if (opeers_shm) {

            opeer_shm = ngx_http_upstream_fastest_find_shm_peer(opeers_shm,
                                                             peer[i].peer_addr);
            if (opeer_shm) {
                ngx_log_debug1(NGX_LOG_DEBUG_HTTP, shm_zone->shm.log, 0,
                               "http upstream fastest, inherit opeer: %V ",
                               &peer[i].peer_addr->name);

                rc = ngx_http_upstream_fastest_init_shm_peer(peer_shm, opeer_shm, pool, &peer[i].peer_addr->name);
                if (rc != NGX_OK) {
                    return NGX_ERROR;
                }

                continue;
            }
        }

        rc = ngx_http_upstream_fastest_init_shm_peer(peer_shm, NULL, pool, &peer[i].peer_addr->name);
        if (rc != NGX_OK) {
            return NGX_ERROR;
        }
    }

    peers->peers_shm = peers_shm;
    shm_zone->data = peers_shm;

    return NGX_OK;

failure:
    ngx_log_error(NGX_LOG_EMERG, shm_zone->shm.log, 0,
                  "http upstream fastest_shm_size is too small, "
                  "you should specify a larger size.");
    return NGX_ERROR;
}


static ngx_int_t
ngx_http_upstream_fastest_init_shm_peer(ngx_http_upstream_fastest_peer_shm_t *psh,
    ngx_http_upstream_fastest_peer_shm_t *opsh,
    ngx_pool_t *pool, ngx_str_t *name)
{
    u_char  *file;

    if (opsh) {
        psh->access_time  = opsh->access_time;
        psh->speeds = opsh->speeds;

    } else{
        psh->access_time  = 0;
        psh->speeds=0;
    }

#if (NGX_HAVE_ATOMIC_OPS)

    file = NULL;

#else

    file = ngx_pnalloc(pool, ngx_cycle->lock_file.len + name->len);
    if (file == NULL) {
        return NGX_ERROR;
    }

    (void) ngx_sprintf(file, "%V%V%Z", &ngx_cycle->lock_file, name);

#endif

    if (ngx_shmtx_create(&psh->mutex, &psh->lock, file) != NGX_OK) {
        return NGX_ERROR;
    }

    return NGX_OK;
}

//在ngx_http_upstream_fastest_peers_shm_t中查找特定addr的ngx_http_upstream_fastest_peer_shm_t

static ngx_http_upstream_fastest_peer_shm_t *
ngx_http_upstream_fastest_find_shm_peer(ngx_http_upstream_fastest_peers_shm_t *p,
    ngx_addr_t *addr)
{
    ngx_uint_t                          i;
    ngx_http_upstream_fastest_peer_shm_t *peer_shm;

    for (i = 0; i < p->number; i++) {

        peer_shm = &p->peers[i];

        if (addr->socklen != peer_shm->socklen) {
            continue;
        }

        if (ngx_memcmp(addr->sockaddr, peer_shm->sockaddr,
                       addr->socklen) == 0) {
            return peer_shm;
        }
    }

    return NULL;
}


static ngx_int_t ngx_http_upstream_fastest_get_shm_name(ngx_str_t *shm_name, ngx_pool_t *pool, ngx_uint_t generation){
    
    u_char  *last;

    shm_name->data = ngx_palloc(pool, SHM_NAME_LEN);
    if (shm_name->data == NULL) {
        return NGX_ERROR;
    }

    last = ngx_snprintf(shm_name->data, SHM_NAME_LEN, "%s#%ui",
                        "ngx_http_upstream_fastest", generation);

    shm_name->len = last - shm_name->data;

    return NGX_OK;
}


static ngx_shm_zone_t *
ngx_shared_memory_find(ngx_cycle_t *cycle, ngx_str_t *name, void *tag)
{
    ngx_uint_t        i;
    ngx_shm_zone_t   *shm_zone;
    ngx_list_part_t  *part;

    part = (ngx_list_part_t *) &(cycle->shared_memory.part);
    shm_zone = part->elts;

    for (i = 0; /* void */ ; i++) {

        if (i >= part->nelts) {
            if (part->next == NULL) {
                break;
            }
            part = part->next;
            shm_zone = part->elts;
            i = 0;
        }

        if (name->len != shm_zone[i].shm.name.len) {
            continue;
        }

        if (ngx_strncmp(name->data, shm_zone[i].shm.name.data, name->len)
                != 0)
        {
            continue;
        }

        if (tag != shm_zone[i].tag) {
            continue;
        }

        return &shm_zone[i];
    }

    return NULL;
}


//----------------------------------负载均衡核心算法------------------------------------------------------------

static ngx_int_t ngx_http_upstream_init_fastest(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us){
    
    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
        return NGX_ERROR;
    }

    us->peer.init = ngx_http_upstream_init_fastest_peer;
    
    return NGX_OK;

}

static ngx_int_t ngx_http_upstream_init_fastest_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us){
    
	ngx_http_upstream_fastest_peer_data_t     *fastestpd;

    ngx_log_debug(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
                   "init fastest peer");

    fastestpd = ngx_palloc(r->pool, sizeof(ngx_http_upstream_fastest_peer_data_t));
    if (fastestpd == NULL) {
        return NGX_ERROR;
    }
    fastestpd->upstream_name = &us->host ;

    r->upstream->peer.data = &fastestpd->rrp;

    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
        return NGX_ERROR;
    }

    r->upstream->peer.get = ngx_http_upstream_get_fastest_peer;
    //r->upstream->peer.free = ngx_http_upstream_free_fastest_peer;

    fastestpd->get_rr_peer = ngx_http_upstream_get_round_robin_peer;
    //fastestpd->free_rr_peer = ngx_http_upstream_free_round_robin_peer;

    return NGX_OK;

}

static ngx_int_t
ngx_http_upstream_get_fastest_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_fastest_peer_data_t  *fastestpd = data;

    time_t                         now;
    uintptr_t                      m;
    ngx_int_t                      rc;
    ngx_uint_t                     i, j, n, p;
    ngx_http_upstream_rr_peer_t   *peer, *best;
    ngx_http_upstream_rr_peers_t  *peers;

    ngx_http_upstream_fastest_peers_t * peers_ctx = fastest_peers_ctx;
    ngx_http_upstream_fastest_peer_t * fastest_peers;

    fastest_peers = peers_ctx->peers.elts;

    ngx_int_t speed, best_speed;

    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "tag:peer get fastest conn peer, try: %ui", pc->tries);

    if (fastestpd->rrp.peers->single) {
        return fastestpd->get_rr_peer(pc, &fastestpd->rrp);
    }

    pc->cached = 0;
    pc->connection = NULL;

    now = ngx_time();

    peers = fastestpd->rrp.peers;

    best = NULL;

    best_speed = 0;
    speed = 0;
    p = 0;

    srandom(ngx_time());

    int random_peer=ngx_random() % peers->number;
    i=random_peer;
    do{
        speed = 0;

        n = i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

        if (fastestpd->rrp.tried[n] & m) {
            continue;
        }

        peer = &peers->peer[i];

        if (peer->down) {
            continue;
        }

        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            continue;
        }

         //结合了权重和响应速度，
         //比较a.speed * b.weight 与 b.speed * a.weight


        for (j = 0; j < peers_ctx->peers.nelts; ++j)
        {

            //判断是否在同一个upstream内
            if (ngx_strncmp(peers->name, fastest_peers[i].upstream_name, peers->name->len) != 0)
            {
                continue;
            }

            //判断是不是同一个server
            if (ngx_strncmp(&peer->name, &fastest_peers[i].peer_addr->name, peer->name.len) != 0)
            {
                continue;
            }

            speed = fastest_peers[i].shm->speeds;
            break;
        }

        if (speed == 0)
        {
            continue;
        }

        if (best == NULL
            || speed * best->weight < best_speed * peer->weight)
        { 
            best = peer;
            best_speed = speed;
            p = i;

        } 

        i++;
        i%=peers->number;

    }while(i!=random_peer);


    if (best == NULL) {
        ngx_log_debug(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get fastest peer, no peer found");

        goto failed;
    }

    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }

    pc->sockaddr = best->sockaddr;
    pc->socklen = best->socklen;
    pc->name = &best->name;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "tag:peer found fastest peer");

    fastestpd->rrp.current = p;

    n = p / (8 * sizeof(uintptr_t));
    m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));

    fastestpd->rrp.tried[n] |= m;

    if (pc->tries == 1 && peers->next) {
        pc->tries += peers->next->number;
    }

    return NGX_OK;

failed:

    if (peers->next) {
        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "tag:peer get fastest peer, backup servers");

        fastestpd->rrp.peers = peers->next;
        pc->tries = fastestpd->rrp.peers->number;

        n = (fastestpd->rrp.peers->number + (8 * sizeof(uintptr_t) - 1))
                / (8 * sizeof(uintptr_t));

        for (i = 0; i < n; i++) {
             fastestpd->rrp.tried[i] = 0;
        }

        rc = ngx_http_upstream_get_fastest_peer(pc, fastestpd);

        if (rc != NGX_BUSY) {
            return rc;
        }
    }

    /* all peers failed, mark them as live for quick recovery */

    for (i = 0; i < peers->number; i++) {
        peers->peer[i].fails = 0;
    }

    pc->name = peers->name;

    return NGX_BUSY;
}


static char *ngx_http_upstream_fastest(ngx_conf_t *cf, ngx_command_t *cmd, void *conf){

    ngx_http_upstream_srv_conf_t  *uscf;

    uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);

    if (uscf->peer.init_upstream) {
        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
                           "tag:peer load balancing method redefined");
    }

    uscf->peer.init_upstream = ngx_http_upstream_init_fastest;

    uscf->flags = NGX_HTTP_UPSTREAM_CREATE
                  |NGX_HTTP_UPSTREAM_WEIGHT
                  |NGX_HTTP_UPSTREAM_MAX_FAILS
                  |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
                  |NGX_HTTP_UPSTREAM_DOWN;

    return NGX_CONF_OK;
}

//------------------------------------获取servers的响应速度----------------------

static ngx_int_t
ngx_http_upstream_fastest_add_timers(ngx_cycle_t *cycle)
{
    ngx_uint_t                           i;
    ngx_msec_t                           t, delay;

    ngx_http_upstream_fastest_peer_t      *peer;
    ngx_http_upstream_fastest_peers_t     *peers;
    ngx_http_upstream_fastest_peer_shm_t  *peer_shm;
    ngx_http_upstream_fastest_peers_shm_t *peers_shm;

    peers = fastest_peers_ctx;
    if (peers == NULL) {


        return NGX_OK;
    }

    peers_shm = peers->peers_shm;
    if (peers_shm == NULL) {
        return NGX_OK;
    }

    ngx_log_debug2(NGX_LOG_DEBUG_HTTP, cycle->log, 0,
                   "tag:zhipcui http fastest upstream init_process, shm_name: %V, "
                   "peer number: %ud",
                   &peers->fastest_shm_name,
                   peers->peers.nelts);

    srandom(ngx_pid);

    peer = peers->peers.elts;
    peer_shm = peers_shm->peers;

    for (i = 0; i < peers->peers.nelts; i++) {
        peer[i].shm = &peer_shm[i];

        peer[i].fastest_ev.handler = ngx_http_upstream_fastest_begin_handler;
        peer[i].fastest_ev.log = cycle->log;
        peer[i].fastest_ev.data = &peer[i];
        peer[i].fastest_ev.timer_set = 0;

        peer[i].fastest_timeout_ev.handler =
            ngx_http_upstream_fastest_timeout_handler;
        peer[i].fastest_timeout_ev.log = cycle->log;
        peer[i].fastest_timeout_ev.data = &peer[i];
        peer[i].fastest_timeout_ev.timer_set = 0;

        peer[i].send_handler = ngx_http_upstream_fastest_peek_handler;
        peer[i].recv_handler = ngx_http_upstream_fastest_peek_handler;

        peer[i].init = NULL;
        peer[i].parse = NULL;
        peer[i].reinit = NULL;

        /*
         * We add a random start time here, since we don't want to trigger
         * the fastest events too close to each other at the beginning.
         */
        delay = 1000;
        t = ngx_random() % delay;

        ngx_add_timer(&peer[i].fastest_ev, t);
    }

    return NGX_OK;
}

static void
ngx_http_upstream_fastest_begin_handler(ngx_event_t *event)
{
    ngx_msec_t                           interval;
    ngx_http_upstream_fastest_peer_t      *peer;
    ngx_http_upstream_fastest_peers_t     *peers;
    ngx_http_upstream_fastest_peers_shm_t *peers_shm;

    if (ngx_http_upstream_fastest_need_exit()) {
        return;
    }

    peers = fastest_peers_ctx;
    if (peers == NULL) {
        return;
    }

    peers_shm = peers->peers_shm;
    if (peers_shm == NULL) {
        return;
    }

    peer = event->data;

    ngx_add_timer(event, 3000 / 2);

    /* This process is processing the events now. */
    if (peer->shm->owner == ngx_pid) {
        return;
    }

    interval = ngx_current_msec - peer->shm->access_time;
    ngx_log_debug5(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest begin handler index: %ui, owner: %P, "
                   "ngx_pid: %P, interval: %M, fastest_interval: %M",
                   peer->index, peer->shm->owner,
                   ngx_pid, interval,
                   3000);

    ngx_shmtx_lock(&peer->shm->mutex);

    if (peers_shm->generation != ngx_http_upstream_fastest_shm_generation) {
        ngx_shmtx_unlock(&peer->shm->mutex);
        return;
    }

    if ((interval >= 3000)
         && (peer->shm->owner == NGX_INVALID_PID))
    {

        peer->shm->owner = ngx_pid;

    } else if (interval >= (3000 << 4)) {

        /*
         * If the fastest peer has been untouched for 2^4 times of
         * the fastest interval, activate the current timer.
         * Sometimes, the fastesting process may disappear
         * in some circumstances, and the clean event will never
         * be triggered.
         */
        peer->shm->owner = ngx_pid;
        peer->shm->access_time = ngx_current_msec;
    }

    ngx_shmtx_unlock(&peer->shm->mutex);


    ngx_log_debug(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest try to connect handler...."
                   );
    if (peer->shm->owner == ngx_pid) {

        ngx_log_debug(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest connect handler...."
                   );
        ngx_http_upstream_fastest_connect_handler(event);
    }
}


static void
ngx_http_upstream_fastest_connect_handler(ngx_event_t *event)
{
    ngx_int_t                            rc;
    ngx_connection_t                    *c;
    ngx_http_upstream_fastest_peer_t      *peer;


    if (ngx_http_upstream_fastest_need_exit()) {
        return;
    }

    peer = event->data;
        ngx_log_debug(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui in  connect handler...."
                   );
        /*ngx_log_debug3(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest connect_handler start, sockaddr:%V, socklen:%ui, name:%V ",
                   peer->peer_addr->sockaddr,
                   peer->peer_addr->socklen,
                   &peer->peer_addr->name
                   );
        */

    ngx_memzero(&peer->pc, sizeof(ngx_peer_connection_t));

    peer->pc.sockaddr = peer->peer_addr->sockaddr;
    peer->pc.socklen = peer->peer_addr->socklen;
    peer->pc.name = &peer->peer_addr->name;

    peer->pc.get = ngx_event_get_peer;
    peer->pc.log = event->log;
    peer->pc.log_error = NGX_ERROR_ERR;

    peer->pc.cached = 0;
    peer->pc.connection = NULL;

    rc = ngx_event_connect_peer(&peer->pc);

    ngx_log_debug(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest connect_handler ----------------------------");


    if (rc == NGX_ERROR || rc == NGX_DECLINED) {
        ngx_http_upstream_fastest_status_update(peer, 0);
        return;
    }

    /* NGX_OK or NGX_AGAIN */
    c = peer->pc.connection;
    c->data = peer;
    c->log = peer->pc.log;
    c->sendfile = 0;
    c->read->log = c->log;
    c->write->log = c->log;
    c->pool = peer->pool;

    peer->state = NGX_HTTP_FASTEST_CONNECT_DONE;

    c->write->handler = peer->send_handler;
    c->read->handler = peer->recv_handler;

    ngx_add_timer(&peer->fastest_timeout_ev, 3000);

    /* The kqueue's loop interface needs it. */
    if (rc == NGX_OK) {
        c->write->handler(c->write);
    }


    ngx_log_debug(NGX_LOG_DEBUG_HTTP, event->log, 0,
                   "tag:zhipcui http fastest connect_handler end");

}

//超时
static void
ngx_http_upstream_fastest_timeout_handler(ngx_event_t *event)
{
    ngx_http_upstream_fastest_peer_t  *peer;

    if (ngx_http_upstream_fastest_need_exit()) {
        return;
    }

    peer = event->data;

    ngx_log_error(NGX_LOG_ERR, event->log, 0,
                  "tag:zhipcui fastest time out with peer: %V ",
                  &peer->fastest_peer_addr->name);

    ngx_http_upstream_fastest_status_update(peer, 0);
    ngx_http_upstream_fastest_clean_event(peer);
}

static void
ngx_http_upstream_fastest_peek_handler(ngx_event_t *event)
{
    char                            buf[1];
    ngx_int_t                       n;
    ngx_err_t                       err;
    ngx_connection_t               *c;
    ngx_http_upstream_fastest_peer_t *peer;

    if (ngx_http_upstream_fastest_need_exit()) {
        return;
    }

    c = event->data;
    peer = c->data;

    n = recv(c->fd, buf, 1, MSG_PEEK);

    err = ngx_socket_errno;

    ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, err,
                   "tag:zhipcui http fastest upstream recv(): %i, fd: %d",
                   n, c->fd);

    if (n >= 0 || err == NGX_EAGAIN) {
        ngx_http_upstream_fastest_status_update(peer, 1);

    } else {
        c->error = 1;
        ngx_http_upstream_fastest_status_update(peer, 0);
    }

    ngx_http_upstream_fastest_clean_event(peer);

    ngx_http_upstream_fastest_finish_handler(event);
}


//更新某个peer的状态
static void
ngx_http_upstream_fastest_status_update(ngx_http_upstream_fastest_peer_t *peer,
    ngx_int_t result)
{

    if (result) {

        peer->shm->speeds = ngx_current_msec - peer->shm->access_time;

    } else {
        peer->shm->speeds = -1;
    }
    peer->shm->access_time = ngx_current_msec;
}

//检查nginx是否在运行，如果已经退出也要退出fastest模块的工作
static ngx_int_t
ngx_http_upstream_fastest_need_exit()
{
    if (ngx_terminate || ngx_exiting || ngx_quit) {
        ngx_http_upstream_fastest_clear_all_events();
        return 1;
    }

    return 0;
}


//结束fastest模块的工作
static void
ngx_http_upstream_fastest_finish_handler(ngx_event_t *event)
{
    if (ngx_http_upstream_fastest_need_exit()) {
        return;
    }
}


static void
ngx_http_upstream_fastest_clean_event(ngx_http_upstream_fastest_peer_t *peer)
{
    ngx_connection_t  *c;

    c = peer->pc.connection;

    ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
                   "tag:zhipcui http fastest clean event: index:%i, fd: %d",
                   peer->index, c->fd);

    ngx_close_connection(c);

    if (peer->fastest_timeout_ev.timer_set) {
        ngx_del_timer(&peer->fastest_timeout_ev);
    }

    peer->state = NGX_HTTP_FASTEST_ALL_DONE;

    if (peer->fastest_data != NULL && peer->reinit) {
        peer->reinit(peer);
    }

    peer->shm->owner = NGX_INVALID_PID;
}


//清除fastest模块的所有监听工作
static void
ngx_http_upstream_fastest_clear_all_events()
{
    ngx_uint_t                       i;
    ngx_connection_t                *c;
    ngx_http_upstream_fastest_peer_t  *peer;
    ngx_http_upstream_fastest_peers_t *peers;

    static ngx_flag_t                has_cleared = 0;

    if (has_cleared || fastest_peers_ctx == NULL) {
        return;
    }

    ngx_log_error(NGX_LOG_NOTICE, ngx_cycle->log, 0,
                  "tag:zhipcui clear all the events on %P ", ngx_pid);

    has_cleared = 1;

    peers = fastest_peers_ctx;

    peer = peers->peers.elts;
    for (i = 0; i < peers->peers.nelts; i++) {

        if (peer[i].fastest_ev.timer_set) {
            ngx_del_timer(&peer[i].fastest_ev);
        }

        if (peer[i].fastest_timeout_ev.timer_set) {
            c = peer[i].pc.connection;
            ngx_close_connection(c);
            ngx_del_timer(&peer[i].fastest_timeout_ev);
        }

        if (peer[i].pool != NULL) {
            ngx_destroy_pool(peer[i].pool);
            peer[i].pool = NULL;
        }
    }
}


//在配置中遇到fastest_status,启用查看状态
static char *
ngx_http_upstream_fastest_status(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{

    ngx_http_core_loc_conf_t            *clcf;

    clcf = ngx_http_conf_get_module_loc_conf(cf, ngx_http_core_module);

    clcf->handler = ngx_http_upstream_fastest_status_handler;

    return NGX_CONF_OK;
}


static ngx_int_t
ngx_http_upstream_fastest_status_handler(ngx_http_request_t *r)
{
    size_t                                 buffer_size;
    ngx_int_t                              rc;
    ngx_buf_t                             *b;
    ngx_chain_t                            out;
    ngx_http_upstream_fastest_peers_t       *peers;

    if (r->method != NGX_HTTP_GET && r->method != NGX_HTTP_HEAD) {
        return NGX_HTTP_NOT_ALLOWED;
    }

    rc = ngx_http_discard_request_body(r);

    if (rc != NGX_OK) {
        return rc;
    }

    ngx_str_t content_type = ngx_string("application/json");
    r->headers_out.content_type = content_type;

    if (r->method == NGX_HTTP_HEAD) {
        r->headers_out.status = NGX_HTTP_OK;

        rc = ngx_http_send_header(r);

        if (rc == NGX_ERROR || rc > NGX_OK || r->header_only) {
            return rc;
        }
    }

    peers = fastest_peers_ctx;
    if (peers == NULL) {
        ngx_log_error(NGX_LOG_ERR, r->connection->log, 0,
                      "tag:zhipcui http upstream fastest module can not find any fastest "
                      "server, make sure you've added the fastest servers");

        return NGX_HTTP_INTERNAL_SERVER_ERROR;
    }

    /* 1/4 pagesize for each record */
    buffer_size = peers->peers.nelts * ngx_pagesize / 4;
    buffer_size = ngx_align(buffer_size, ngx_pagesize) + ngx_pagesize;

    b = ngx_create_temp_buf(r->pool, buffer_size);
    if (b == NULL) {
        return NGX_HTTP_INTERNAL_SERVER_ERROR;
    }

    out.buf = b;
    out.next = NULL;

    ngx_http_upstream_fastest_status_json_format(b, peers);

    r->headers_out.status = NGX_HTTP_OK;
    r->headers_out.content_length_n = b->last - b->pos;

    if (r->headers_out.content_length_n == 0) {
        r->header_only = 1;
    }

    b->last_buf = 1;

    rc = ngx_http_send_header(r);

    if (rc == NGX_ERROR || rc > NGX_OK || r->header_only) {
        return rc;
    }

    return ngx_http_output_filter(r, &out);
}

//输出json格式的响应
static void
ngx_http_upstream_fastest_status_json_format(ngx_buf_t *b,
    ngx_http_upstream_fastest_peers_t *peers)
{
    ngx_uint_t                       count, i, last;
    ngx_http_upstream_fastest_peer_t  *peer;

    peer = peers->peers.elts;

    count = 0;

    for (i = 0; i < peers->peers.nelts; i++) {

        count++;
    }

    b->last = ngx_snprintf(b->last, b->end - b->last,
            "{\"servers\": {\n"
            "  \"total\": %ui,\n"
            "  \"generation\": %ui,\n"
            "  \"server\": [\n",
            count,
            ngx_http_upstream_fastest_shm_generation);

    last = peers->peers.nelts - 1;
            
    for (i = 0; i < peers->peers.nelts; i++) {

        b->last = ngx_snprintf(b->last, b->end - b->last,
                "    {\"index\": %ui, "
                "\"upstream\": \"%V\", "
                "\"name\": \"%V\", "
                "\"speeds\": \"%i\"} "
                "%s\n",
                i,
                peer[i].upstream_name,
                &peer[i].peer_addr->name,
                peer[i].shm->speeds,
                (i == last) ? "" : ",");
    }

    b->last = ngx_snprintf(b->last, b->end - b->last,
            "  ]\n");

    b->last = ngx_snprintf(b->last, b->end - b->last,
            "}}\n");
}


static ngx_int_t
ngx_http_upstream_fastest_init_process(ngx_cycle_t *cycle)
{
    return ngx_http_upstream_fastest_add_timers(cycle);
}




